package com.LeeCode;

import java.util.List;
import java.util.TreeMap;

/**
 * 最小正和子数组
 */

public class Code3364 {
    public static void main(String[] args) {

    }

    public int minimumSumSubarray(List<Integer> nums, int l, int r) {
        int n = nums.size();
        int minSum = Integer.MAX_VALUE;
        boolean found = false;

        // 遍历所有可能的子数组
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums.get(j);
                int length = j - i + 1;

                // 检查长度是否在范围内且和大于0
                if (length >= l && length <= r && sum > 0) {
                    minSum = Math.min(minSum, sum);
                    found = true;
                }

                // 如果长度已经超过r，提前结束内层循环
                if (length > r) {
                    break;
                }
            }
        }

        return found ? minSum : -1;
    }

    private int minimumSumSubarray2(List<Integer> nums, int l, int r) {
        Integer[] a = nums.toArray(Integer[]::new);
        int ans = Integer.MAX_VALUE;
        int n = a.length;
        int[] s = new int[n + 1];
        TreeMap<Integer, Integer> cnt = new TreeMap<>();
        for (int j = 1; j <= n; j++) {
            s[j] = s[j - 1] + a[j - 1];
            if (j < l) {
                continue;
            }
            cnt.merge(s[j - l], 1, Integer::sum); // cnt[s[j-l]]++
            Integer lower = cnt.lowerKey(s[j]); // 返回严格小于s[j]的最大键
            if (lower != null) {
                ans = Math.min(ans, s[j] - lower);
            }
            if (j >= r) {
                int v = s[j - r];
                cnt.merge(v,-1,(old, delta) ->{
                    int res = old + delta;
                    return res == 0? null : res;
                });
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
